import java.util.ArrayList;import java.util.Collections;import java.util.List;
class OrderedStream {

    class TreeArray{
        int[] arr;

        int len;
        TreeArray(int n){
            arr = new int[n + 1];
            len = n;
        }

        int lowBit(int x) {
            return x&(-x);
        }

        void add(int i, int value) {  //构造树状数组的前缀和
            while (i <= len) {
                arr[i] += value;  //当前节点加value
                i += lowBit(i);  //子节加value，在他之上的父节点也要加value;
            }
        }

        int getSum(int i) {   //求前缀和
            int sum = 0;
            while(i > 0) {
                sum += arr[i];
                i -= lowBit(i);
            }
            return sum;
        }

    }


    TreeArray treeArray;

    int ptr = 1;

    String[] strArr;

    int len;

    public OrderedStream(int n) {
        len = n;
        treeArray = new TreeArray(n);
        strArr = new String[n + 1];
    }


    private int binarySearch(int left, int right){
        while(left <= right){
            int mid = (left + right + 1) / 2;
            int prefix = treeArray.getSum(mid);
            if(prefix < mid){
                right = mid - 1;
            } else{
                left = mid;
            }
        }
        return left;
    }

    public List<String> insert(int idKey, String value) {
        treeArray.add(idKey, 1);
        strArr[idKey] = value;
        int fullInd = binarySearch(ptr - 1, len);
        if(fullInd >= ptr){
            List<String> res = new ArrayList<>(fullInd - ptr + 1);
            for(int i = ptr; i <= fullInd; i++) {
                res.add(strArr[i]);
            }
            ptr = fullInd + 1;
            return res;
        }
        return Collections.emptyList();
    }
}
